package class09;

import java.util.PriorityQueue;

/**
 * 堆和排序是解决贪心算法最常用的工具
 *
 * 一块金条切成两半, 是需要花费和长度数值一样的铜板的
 * 比如长度为20的金条,不管怎么切,都要花费20个铜板.一群人想整分整块金条,怎么分最省铜板
 *
 * 例如,给定数组{10,20,30},代表一共3个人,整块金条长度为60,金条要分成10,20,30三个部分
 * 如果先把长度60的金条分成10和50,花费60;再把长度50的金条分成20和30,花费50;一共110铜板
 * 如果先把长度60的金条分成30和30,花费60;再把长度30的金条分成10和20,花费30;一共90铜板
 * 输入一个数组,返回分割的最小代价
 *
 * 贪心策略: 尽可能平均
 * 1.将数组中数据全放入小根堆中
 * 2.先弹出两个, 把两个数的和放回小根堆, 和进行累加(代价 X)
 * 3.第二步周而复始, 直至小根堆中只剩下一个数就停止, 累加的和就是最小代价(X)
 *
 *
 * {10,20,30}
 * 10 + 20 = 30 , X=30
 * 放入30
 * 30 + 30 = 60 , X+=60=30+60=90
 *
 */
public class Code03_LessMoneySplitGold {

	//全排列
	public static int lessMoney1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		return process(arr, 0);
	}

	public static int process(int[] arr, int pre) {
		if (arr.length == 1) {
			return pre;
		}
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
			}
		}
		return ans;
	}

	public static int[] copyAndMergeTwo(int[] arr, int i, int j) {
		int[] ans = new int[arr.length - 1];
		int ansi = 0;
		for (int arri = 0; arri < arr.length; arri++) {
			if (arri != i && arri != j) {
				ans[ansi++] = arr[arri];
			}
		}
		ans[ansi] = arr[i] + arr[j];
		return ans;
	}

	//小根堆
	public static int lessMoney2(int[] arr) {
		PriorityQueue<Integer> pQ = new PriorityQueue<>();
		for (int i = 0; i < arr.length; i++) {
			pQ.add(arr[i]);
		}
		//
		int sum = 0;
		int cur = 0;
		while (pQ.size() > 1) {
			//弹出数的代价和
			cur = pQ.poll() + pQ.poll();
			//代价累计结果
			sum += cur;
			pQ.add(cur);
		}
		return sum;
	}

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (Math.random() * (maxValue + 1));
		}
		return arr;
	}

	public static void main(String[] args) {
		int testTime = 100000;
		int maxSize = 6;
		int maxValue = 1000;
		for (int i = 0; i < testTime; i++) {
			int[] arr = generateRandomArray(maxSize, maxValue);
			if (lessMoney1(arr) != lessMoney2(arr)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}
